/**
 * 
 */
package dp.passed;

/**
 * @author xyyi
 *
 */
public class MinimumPathSum {
	/**
	Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

	Note: You can only move either down or right at any point in time.
	 */
	// DP modified original grid with time O(rows * cols)
	public int minPathSum(int[][] grid) {
		if (grid == null || grid.length == 0)
			return 0;
		int rows = grid.length, cols = grid[0].length;

		for (int row = 0; row < rows; row++) {
			for (int col = 0; col < cols; col++) {
				if (row == 0 && col == 0)
					continue;
				if (row == 0)
					grid[row][col] += grid[row][col - 1];
				else if (col == 0)
					grid[row][col] += grid[row - 1][col];
				else
					grid[row][col] = grid[row][col]
							+ Math.min(grid[row - 1][col], grid[row][col - 1]);
			}
		}

		return grid[rows - 1][cols - 1];
	}

	// DP without changing original grid, time (rows * cols), space(cols) or space(rows)
	public int minPathSumDP(int[][] grid) {
		if (grid == null || grid.length == 0)
			return 0;

		int rows = grid.length, cols = grid[0].length;
		int[] dp = new int[cols + 1];
		for (int i = 0; i <= cols; i++) {
			dp[i] = Integer.MAX_VALUE;
		}
		dp[1] = 0;
		for (int row = 0; row < rows; row++) {
			for (int col = 0; col < cols; col++) {
				dp[col + 1] = Math.min(dp[col + 1], dp[col]) + grid[row][col];
			}
		}

		return dp[cols];
	}

	/**
	 * 
	 */
	public MinimumPathSum() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		MinimumPathSum mps = new MinimumPathSum();
		int[][] grid = { { 1, 2 }, { 1, 1 } };
		int min = mps.minPathSumDP(grid);
		System.out.printf("%d\n", min);
	}
}
